# InsertionSort20211017.py
# 位置 1
#           vi=1  len(array) - 1
#  0  1  2
# [2, 3, 5, 6, 8, 9]
#     ^j
#  ^j-1
# 插入排序
def insertion_sort(array):
  for i in range(1, len(array)):
    j = i

    while array[j - 1] > array[j] and j >= 1:
      array[j - 1], array[j] = array[j], array[j - 1]
      j -= 1

  return array

print(insertion_sort([8, 5, 2, 9, 6, 3]))
